This invention relates generally to asynchronous register systems as used in the computing field. More specifically, it relates to asynchronous register systems in which data signals are transfered bi-directionally without regard to clock signals or other timing devices, rather, the speed of operation for an asynchronous system is determined essentially by the speed of the circuitry within the system. Consequently, the asynchronous nature of the system of the present invention allows its embodiments to operate at the maximum speed of the circuitry in such embodiments.
Recognizing the numerous advantages of asynchronous or self-timed data processing systems, the parent case hereto discloses a new form of data control for asynchronous operation utilizing retrograde data paths. The data structure is disclosed in the parent case as used in a so-called FIFO system or register. The present invention is based on the recognition of the capability of such data structures to be used in sequences or strings with reciprocal control so as to effect control and registration. While the parent case disclosed a first-in-first-out register (FIFO) the disclosed embodiment of the present invention is a so-called "queue" register.
FIFO systems (first-in, first-out registers) are used in computers to provide time independence between the processing operations preceding and following the FIFO. Essentially, a FIFO is used to decouple a processor before it from the one following it. Accordingly, a FIFO can deliver data to a later processor even if the earlier process has temporarily halted. Similarly, a FIFO can hold data from a preceding processor while a later unit is temporarily unable to accept data. The independence of these systems from timing clocks enables such operations.
Clocking operations in computers inherently raise numerous problems; however, most prior computing systems were built with clocked logic. Each step in the computing process proceeds according to the beat of the clock; identical clock signals are delivered to all parts of the system, just as identical drum beats are delivered to all men in a marching column. On the contrary in the system hereof, elements of data move forward without clocking delays, however, with due regard to avoiding destruction of other data in the sequence. As recognized in the parent case, the control of a string of individual cells (for elements of data) with retrograde flow may be implemented to consider the state of a predecessor cell and that of a successor cells, remaining ignorant of other global conditions. The present invention involves an embellishment of that concept.
In general, two types of local control can be employed in sequential systems to preserve orderly movement of data. According to one type of control, the same wires that carry data signals from one cell to the next cell also carry control information. Such mechanisms are usually designed for systems that carry data elements of only a single bit. Such a one-bit sequential system (with data and control carried on the same wires) is called a "queue". Queues can be designed to carry multiple bit data elements, but additional logic is required for such systems.
Recapitulating to some extent, consider further the substance of the present invention as related to the parent case. The asynchronous FIFO and asynchronous queue are somewhat similar structures in that both can provide temporary storage for data moving between systems that operate at offset speeds. The registers are different in one main aspect: in addition to data paths, the FIFO incorporates extra (separate but parallel) control paths to carry control signals representative of the presence or absence of data on the data paths. In distinction, the queue, as described herein, uses the same signalling paths for both data and control.
Considering another generality, FIFOs traditionally are used where data elements are composed of a multiplicity of individual binary bits. Such data elements are generally called "words" and the number of bits in each such element is called the "width" of the word. A queue is generally most useful when the data elements consist of a single bit, or at most a few bits, that is, when the words are one bit wide or at least quite narrow
As indicated above, it is generally characteristic of a queue that the same signal paths are used for both data and control. In that regard, it has been previously recognized that signal paths in a queue must be capable of transmitting more than two states. For example, in U.S. Pat. No. 3,166,715 (Cogar), a system is described in which two wires transmit binary codes to manifest spaces between bits. A subsequent patent by the same inventor (U.S. Pat. No. 3,510,680) discloses the use of pulses rather than level codes. In that regard, most previous queues have related data values to signal levels. For example, one signal level may represent a logical zero, another level represents a logical one. Such systems relating data values to signal levels might involve the action of electrical current, fluid signals or any of a variety of other binary criteria.
In accordance with the present invention, contrasting to traditional binary queues, information is represented in terms of changes in signal level. That is, each change in one signal represents a logical "one". Similarly, each change in another signal represents a logical "zero". In accordance herewith, sequencing in the two paths is controlled by reciprocal couplings in the structure.
As information is carried by transitions between signal levels in the system of the present invention, each such transition representing data, the system is able to transmit one bit of information per signal level transition. Conversely, previously known systems utilizing signal levels to represent information, have required two transitions per bit transmitted. In that regard, the present invention is distinct from prior systems. Furthermore, the system of the present invention provides for retrograde transmission of data values.
The operation of an asynchronous transition queue as described herein can be explained preliminarily in terms of a group of men and women, each performing tasks in accordance with a precise and specific instruction. Of course, as disclosed in detail below, the system would be practically implemented utilizing any of a variety of electrical, mechanical, optical, pneumatic, biological or other logic structures.
Pursuing the exemplary human queue, suppose that two lines are formed, one consisting of women, the other consisting of men. In the example, men register "zero" bits, while women register "one" bits. Such registrations are accomplished by the action of raising or lowering the hands. For example, a male transition is accomplished when a man moves his hand indicating a change in the "zero" channel. Similarly, a change is indicated in the "ones" channel by a female transition when a woman moves her hands.
Each man associates with a particular woman to function as a singular data cell. Accordingly, each couple can transmit a binary "one" by a female transition, and a binary "zero" by a male transition.
In the alignment, each couple will have a predecessor couple and a successor couple. Thus, each individual has a partner of the opposite sex and a predecessor and a successor of the same sex. In such a configuration, the assumed group can act as a queue by each following a simple rule of behavior. Essentially, the behavior rule commands that each person will copy the position of his predecessor person (to pass information forward) but will avoid overtaking previously passed information. The rule of behavior is a modification of a behavior rule set forth in the parent case. Specifically, in accordance herewith, the rule may be stated for each person (except the first and last) as follows: if your predecessor and successor are in opposite states, and the states of your partner's predecessor and successor match, then copy the state of your predecessor, otherwise remain as you stand.
Suppose that all the people begin with their hands down. If the first man is instructed to raise his hands (representing a binary "zero"), the second man (acting on the rule) would be obliged to raise his hands, thus obliging the third man to raise his hands, and so on throughout the line until all the men have raised their hands. Assume for the moment that as the output element, the final man in the line may not lower his hands until such lowering is approved by an instruction from the output.
Now suppose that another transition is introduced into the men's row, representing a second binary "zero". The second "zero" is represented by the first man lowering his hands. The wave of hand lowering will proceed to and include the next to the last man. Recall that for the moment the last man remains with his hands up until an external signal allows a change.
With the introduction of a third binary "zero", another wave of hand moving occurs, in this instance, another raising of the hands. Thus, as the process of entering binary "zeros" proceeds, each new wave (representing an additional binary "zero") moves through the male portion of the human queue stopping at the end of the queue where data is registered. Consequently, the males at the end of the register stand configured alternately with hands raised and hands lowered.
Now, in addition to the "zeros" registered by the males, consider an action by the women to register "ones". Upon the introduction of a "one", the first woman raises her hands. Immediately, the second woman is obliged to follow her instruction raising her hands to join the first. Accordingly, a "ones" wave propagates through the line of women down the queue. However, when the wave reaches the man configured to register a "one", it encounters a situation of the woman's partner's (man's) predecessor and successor, being in opposite states. Consequently, the rule of behavior obligates the woman at that stage to do nothing. And so the situation develops with "zeros" registered by men at the end of the line and "ones" registered by women behind them. Thus, an orderly registration configuration is accomplished.
The human analogy illustrates the relatively simple instruction for individual data units in the sequences, one of which accommodate "zeros", while the other accommodates ones. Their functionally interrelated instructions based upon predecessor and successor states, affords the somewhat basic operation of the system of the present invention, as set forth in detail with respect to the disclosed embodiment.